<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>数据结构和算法5-非线性-树 | iworkh blog</title>
  
    <meta name="keywords" content=" 结构和算法 ">
  
  <meta name="description" content="数据结构和算法5-非线性-树 | iworkh blog">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="个人简介沐雨云楼，程序员一名。 喜欢研究技术，主要从事JAVA、微服务、大数据领域。 联系方式 QQ : 157162006 邮箱 :157162006@qq.com">
<meta property="og:type" content="website">
<meta property="og:title" content="关于">
<meta property="og:url" content="https://iworkh.gitee.io/blog/about/index.html">
<meta property="og:site_name" content="iworkh blog">
<meta property="og:description" content="个人简介沐雨云楼，程序员一名。 喜欢研究技术，主要从事JAVA、微服务、大数据领域。 联系方式 QQ : 157162006 邮箱 :157162006@qq.com">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-05-17T07:22:16.000Z">
<meta property="article:modified_time" content="2020-09-12T13:21:47.523Z">
<meta property="article:author" content="沐雨云楼">
<meta property="article:tag" content="iworkh">
<meta property="article:tag" content="沐雨云楼">
<meta property="article:tag" content="blog">
<meta name="twitter:card" content="summary">


<link rel="icon" href="/blog/img/iwork.svg">

<link href="/blog/css/style.css?v=1.0.1" rel="stylesheet">

<link href="/blog/css/hl_theme/atom-light.css?v=1.0.1" rel="stylesheet">

<link href="//cdn.bootcdn.net/ajax/libs/animate.css/4.1.0/animate.min.css" rel="stylesheet">
<link href="//cdn.bootcdn.net/ajax/libs/font-awesome/5.13.0/js/fontawesome.min.js" rel="stylesheet">

<script src="//cdn.bootcdn.net/ajax/libs/jquery/3.5.1/jquery.min.js"></script>
<script src="/blog/js/jquery.autocomplete.min.js?v=1.0.1" ></script>
<script src="/blog/js/titleTip.js?v=1.0.1" ></script>

<script src="//cdn.bootcdn.net/ajax/libs/highlight.js/10.0.3/highlight.min.js"></script>
<script>
    hljs.initHighlightingOnLoad();
</script>

<script src="//cdn.bootcdn.net/ajax/libs/nprogress/0.2.0/nprogress.min.js"></script>



<script src="//cdn.bootcdn.net/ajax/libs/jquery-cookie/1.4.1/jquery.cookie.min.js" ></script>

<script src="/blog/js/iconfont.js?v=1.0.1" ></script>

<meta name="generator" content="Hexo 4.2.1"></head>
<div style="display: none">
  <input class="theme_disqus_on" value="false">
  <input class="theme_preload_comment" value="false">
  <input class="theme_blog_path" value="/blog">
</div>




<body>
<aside class="nav">
    <div class="nav-left">
        <a href="/blog/" class="avatar_target">
    <img class="avatar" src="/blog/img/iwork.svg" />
</a>
<div class="author">
    <span>沐雨云楼</span>
</div>

<div class="icon">
    
        
        <a title="github" href="https://gitee.com/iworkh" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-github"></use>
                </svg>
            
        </a>
        
    
        
        <a title="csdn" href="https://blog.csdn.net/u011622109" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-csdn"></use>
                </svg>
            
        </a>
        
    
        
        <a title="email" href="mailto:157162006@qq.com" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-email"></use>
                </svg>
            
        </a>
        
    
        
        <a title="qq" href="http://wpa.qq.com/msgrd?v=3&uin=157162006&site=qq&menu=yes" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-qq"></use>
                </svg>
            
        </a>
        
    
        
        <a title="kugou" href="https://www.kugou.com/" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-kugou"></use>
                </svg>
            
        </a>
        
    
        
        <a title="neteasemusic" href="https://music.163.com/" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-neteasemusic"></use>
                </svg>
            
        </a>
        
    
</div>



<a class="more-menus">更多菜单</a>


<ul>
    <li><div class="all active">全部文章<small>(85)</small></div></li>
    
        
            
            <li><div data-rel="手册"><i class="fold iconfont icon-right"></i>手册<small>(2)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="iworkh">iworkh<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="pgmanor">pgmanor<small>(1)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="工具"><i class="fold iconfont icon-right"></i>工具<small>(16)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="git">git<small>(2)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="github">github<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="hexo">hexo<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="idea">idea<small>(2)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="markdowm">markdowm<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="maven">maven<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="有道云">有道云<small>(1)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="java"><i class="fold iconfont icon-right"></i>java<small>(20)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="dao">dao<small>(6)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="jvm">jvm<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="test">test<small>(5)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="tools">tools<small>(3)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="并发">并发<small>(1)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="微服务"><i class="fold iconfont icon-right"></i>微服务<small>(6)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="spring">spring<small>(2)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="springboot">springboot<small>(3)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="架构">架构<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="大数据"><i class="fold iconfont icon-right"></i>大数据<small>(4)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="hadoop">hadoop<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="spark">spark<small>(3)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="web"><i class="fold iconfont icon-right"></i>web<small>(3)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="vue">vue<small>(2)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="db"><i class="fold iconfont icon-right"></i>db<small>(4)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="mysql">mysql<small>(3)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="redis">redis<small>(1)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="ai">ai<small>(4)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="python"><i class="fold iconfont icon-right"></i>python<small>(8)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="tornado">tornado<small>(3)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="linux"><i class="fold iconfont icon-right"></i>linux<small>(2)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="docker">docker<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="nginx">nginx<small>(1)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="windows">windows<small>(3)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="结构和算法">结构和算法<small>(8)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="面试">面试<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="其他">其他<small>(1)</small></div>
                
            </li>
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
</ul>
<div class="left-bottom">
    <div class="menus">
    
    
    
    <a class="dynamic-menu " target="_blank"  href="https://pgmanor.gitee.io/blog/">pgmanor</a>
    
    
    <a class="dynamic-menu " target="_blank"  href="https://www.iworkh.com/manualIt/Category/scopeDev/">iworkh</a>
    
    
    <a class="dynamic-menu " target="_blank"  href="https://gitee.com/iworkh">gitee</a>
    
    </div>
    <div><a class="about  hasFriend  site_url"  href="/blog/about">关于</a><a style="width: 50%"  class="friends">友链</a></div>
</div>
<input type="hidden" id="iworkh_site_posts_number" value="85">
<input type="hidden" id="iworkh_site_word_count" value="197.8k">
<div style="display: none">
    <span id="busuanzi_value_site_uv"></span>
    <span id="busuanzi_value_site_pv"></span>
</div>

    </div>
    <div class="nav-right">
        <div class="friends-area">
    <div class="friends-title">
        友情链接
        <i class="back-title-list"></i>
    </div>
    <div class="friends-content">
        <ul>
            
            <li><a target="_blank" href="https://www.iworkh.com">iworkh</a></li>
            
            <li><a target="_blank" href="https://www.iworkh.com/download/share/">下载地址</a></li>
            
            <li><a target="_blank" href="http://yelog.org/">叶落阁</a></li>
            
        </ul>
    </div>
</div>
        <div class="title-list">
    <form onkeydown="if(event.keyCode === 13){return false;}">
        <input id="local-search-input" class="search" type="text" placeholder="in: 开头全文搜索" />
        <i class="cross"></i>
        <span>
            <label for="tagswitch">T:</label>
            <input id="tagswitch" type="checkbox" style="display: none" />
            <i id="tagsWitchIcon"></i>
        </span>
    </form>
    <div class="tags-list">
    
    <li class="article-tag-list-item">
        <a class="color3">ai</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">attr</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">aysnc</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">beanmap</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">bigdecimal</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">blog</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">chrome</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">dict</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">dll</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">docker</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">domain</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">fastjson</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">func</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">git</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">github</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">hadoop</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">hexo</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">idea</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">iworkh</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">jackson</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">java</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">jdni</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">jfinalshell</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">joplin</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">JPA</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">lock</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">markdowm</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">maven</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">mock</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">mq</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">mycat</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">mysql</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">nginx</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">notebook</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">plan</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">powermock</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">python</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">redis</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">rest</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">sharding-jdbc</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">spark</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">springboot</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">test</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">tool</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">tools</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">tornado</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">transactional</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">web</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">windows</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">wtforms</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">zookeeper</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">分库分表</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">分页</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">命令</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">工具</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">并发</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">序列化</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">微服务</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">性能分析</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">手册</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">有道云</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">标签</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">模板</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">百度云盘</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">结构和算法</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">计划</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">迁移</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">面试</a>
    </li>
    
    <div class="clearfix"></div>
</div>

    
    <div id="local-search-result">

    </div>
    
    <nav id="title-list-nav">
        
        <a id="top" class="手册 pgmanor "
           href="/blog/2020/12/15/redirect-to-pgmanor/"
           data-tag="迁移"
           data-author="沐雨云楼" >
            <span class="post-title" title="😘博客迁移">😘博客迁移</span>
            <span class="post-date" title="2020-12-15 23:47:55">2020/12/15</span>
        </a>
        
        <a id="top" class="手册 iworkh "
           href="/blog/2020/05/27/manual-iworkh/"
           data-tag="手册,iworkh"
           data-author="沐雨云楼" >
            <span class="post-title" title="iworkh所有手册">iworkh所有手册</span>
            <span class="post-date" title="2020-05-27 21:37:04">2020/05/27</span>
        </a>
        
        <a id="top" class="微服务 springboot "
           href="/blog/2020/06/27/spring_boot_all_resources/"
           data-tag="springboot"
           data-author="沐雨云楼" >
            <span class="post-title" title="Spring Boot全网优质教程汇总">Spring Boot全网优质教程汇总</span>
            <span class="post-date" title="2020-06-27 17:43:13">2020/06/27</span>
        </a>
        
        <a id="top" class="工具 "
           href="/blog/2020/06/22/baidu-pandisk-share/"
           data-tag="百度云盘"
           data-author="沐雨云楼" >
            <span class="post-title" title="百度云盘分享链接">百度云盘分享链接</span>
            <span class="post-date" title="2020-06-22 18:38:21">2020/06/22</span>
        </a>
        
        <a id="top" class="工具 "
           href="/blog/2020/06/21/tool_blogs_all/"
           data-tag="blog"
           data-author="沐雨云楼" >
            <span class="post-title" title="优质博客和文章">优质博客和文章</span>
            <span class="post-date" title="2020-06-21 20:02:14">2020/06/21</span>
        </a>
        
        <a id="top" class="java jvm "
           href="/blog/2020/06/04/java-online-analysis/"
           data-tag="性能分析"
           data-author="沐雨云楼" >
            <span class="post-title" title="JAVA线上故障排查全套路">JAVA线上故障排查全套路</span>
            <span class="post-date" title="2020-06-04 20:34:05">2020/06/04</span>
        </a>
        
        <a id="top" class="工具 idea "
           href="/blog/2020/05/31/jetbrains-idea/"
           data-tag="工具,idea"
           data-author="沐雨云楼" >
            <span class="post-title" title="idea使用技巧">idea使用技巧</span>
            <span class="post-date" title="2020-05-31 16:12:30">2020/05/31</span>
        </a>
        
        <a id="top" class="工具 有道云 "
           href="/blog/2020/05/18/youdao_config_edit/"
           data-tag="工具,有道云"
           data-author="沐雨云楼" >
            <span class="post-title" title="有道云配置修改">有道云配置修改</span>
            <span class="post-date" title="2020-05-18 21:37:04">2020/05/18</span>
        </a>
        
        <a id="top" class="web "
           href="/blog/2020/06/01/web-tools/"
           data-tag="web,tool"
           data-author="沐雨云楼" >
            <span class="post-title" title="前端常用工具">前端常用工具</span>
            <span class="post-date" title="2020-06-01 21:37:04">2020/06/01</span>
        </a>
        
        <a  class="工具 "
           href="/blog/2020/10/25/tool-linux-jfinalshell/"
           data-tag="jfinalshell"
           data-author="沐雨云楼" >
            <span class="post-title" title="linux连接工具jfinalshell">linux连接工具jfinalshell</span>
            <span class="post-date" title="2020-10-25 10:24:59">2020/10/25</span>
        </a>
        
        <a  class="微服务 springboot "
           href="/blog/2020/10/06/spring-boot-multi-profiles/"
           data-tag="springboot"
           data-author="沐雨云楼" >
            <span class="post-title" title="springboot多环境配置打包">springboot多环境配置打包</span>
            <span class="post-date" title="2020-10-06 21:36:42">2020/10/06</span>
        </a>
        
        <a  class="web vue "
           href="/blog/2020/10/06/vue_springboot_package_publish/"
           data-tag="maven"
           data-author="沐雨云楼" >
            <span class="post-title" title="vue+springboot打包发布">vue+springboot打包发布</span>
            <span class="post-date" title="2020-10-06 14:22:29">2020/10/06</span>
        </a>
        
        <a  class="java dao "
           href="/blog/2020/10/06/java-jpa-query/"
           data-tag="JPA"
           data-author="沐雨云楼" >
            <span class="post-title" title="JPA自定义sql">JPA自定义sql</span>
            <span class="post-date" title="2020-10-06 10:20:38">2020/10/06</span>
        </a>
        
        <a  class="微服务 spring "
           href="/blog/2020/10/03/spring-pageable/"
           data-tag="分页"
           data-author="沐雨云楼" >
            <span class="post-title" title="vue+springboot分页交互">vue+springboot分页交互</span>
            <span class="post-date" title="2020-10-03 11:08:21">2020/10/03</span>
        </a>
        
        <a  class="工具 "
           href="/blog/2020/10/02/chrome-plugin/"
           data-tag="chrome"
           data-author="沐雨云楼" >
            <span class="post-title" title="chrome插件">chrome插件</span>
            <span class="post-date" title="2020-10-02 10:11:31">2020/10/02</span>
        </a>
        
        <a  class="windows "
           href="/blog/2020/10/01/windows-less-dll/"
           data-tag="dll"
           data-author="沐雨云楼" >
            <span class="post-title" title="windows缺少dll">windows缺少dll</span>
            <span class="post-date" title="2020-10-01 20:22:28">2020/10/01</span>
        </a>
        
        <a  class="java "
           href="/blog/2020/09/13/java-base-bigdecimal/"
           data-tag="bigdecimal"
           data-author="沐雨云楼" >
            <span class="post-title" title="BigDecimal正确使用了吗?">BigDecimal正确使用了吗?</span>
            <span class="post-date" title="2020-09-13 10:28:54">2020/09/13</span>
        </a>
        
        <a  class="windows "
           href="/blog/2020/09/12/windows-dev-install/"
           data-tag="windows"
           data-author="沐雨云楼" >
            <span class="post-title" title="windows开发环境安装">windows开发环境安装</span>
            <span class="post-date" title="2020-09-12 21:39:01">2020/09/12</span>
        </a>
        
        <a  class="工具 "
           href="/blog/2020/09/06/tool-notebook-joplin/"
           data-tag="joplin"
           data-author="沐雨云楼" >
            <span class="post-title" title="joplin笔记">joplin笔记</span>
            <span class="post-date" title="2020-09-06 20:50:55">2020/09/06</span>
        </a>
        
        <a  class="web vue "
           href="/blog/2020/09/05/vue-element-admin/"
           data-tag="web"
           data-author="沐雨云楼" >
            <span class="post-title" title="vue element admin开发">vue element admin开发</span>
            <span class="post-date" title="2020-09-05 11:01:38">2020/09/05</span>
        </a>
        
        <a  class="工具 "
           href="/blog/2020/09/05/tool-notebook/"
           data-tag="notebook"
           data-author="沐雨云楼" >
            <span class="post-title" title="常见笔记软件">常见笔记软件</span>
            <span class="post-date" title="2020-09-05 10:54:34">2020/09/05</span>
        </a>
        
        <a  class="java dao "
           href="/blog/2020/08/30/java-dao-shardingSphere/"
           data-tag="sharding-jdbc"
           data-author="沐雨云楼" >
            <span class="post-title" title="分库分表中间件-ShardingSphere">分库分表中间件-ShardingSphere</span>
            <span class="post-date" title="2020-08-30 21:52:45">2020/08/30</span>
        </a>
        
        <a  class="java dao "
           href="/blog/2020/08/30/java-dao-mycat/"
           data-tag="mycat"
           data-author="沐雨云楼" >
            <span class="post-title" title="分库分表中间件-MyCat">分库分表中间件-MyCat</span>
            <span class="post-date" title="2020-08-30 15:01:59">2020/08/30</span>
        </a>
        
        <a  class="java dao "
           href="/blog/2020/08/30/java-dao-sharding-db/"
           data-tag="分库分表"
           data-author="沐雨云楼" >
            <span class="post-title" title="分库分表中间件-开源产品">分库分表中间件-开源产品</span>
            <span class="post-date" title="2020-08-30 09:37:18">2020/08/30</span>
        </a>
        
        <a  class="java dao "
           href="/blog/2020/08/29/java-jndi/"
           data-tag="jdni"
           data-author="沐雨云楼" >
            <span class="post-title" title="JNDI">JNDI</span>
            <span class="post-date" title="2020-08-29 17:12:03">2020/08/29</span>
        </a>
        
        <a  class="工具 git "
           href="/blog/2020/08/27/tool-git-setting/"
           data-tag="git"
           data-author="沐雨云楼" >
            <span class="post-title" title="git配置">git配置</span>
            <span class="post-date" title="2020-08-27 21:30:17">2020/08/27</span>
        </a>
        
        <a  class="java test "
           href="/blog/2020/08/23/java-powermock/"
           data-tag="powermock"
           data-author="沐雨云楼" >
            <span class="post-title" title="powermock测试框架">powermock测试框架</span>
            <span class="post-date" title="2020-08-23 12:45:17">2020/08/23</span>
        </a>
        
        <a  class="java test "
           href="/blog/2020/08/23/java-mockito/"
           data-tag="mock"
           data-author="沐雨云楼" >
            <span class="post-title" title="👍mockito测试框架">👍mockito测试框架</span>
            <span class="post-date" title="2020-08-23 10:45:17">2020/08/23</span>
        </a>
        
        <a  class="java test "
           href="/blog/2020/08/22/java-test-ng/"
           data-tag="test"
           data-author="沐雨云楼" >
            <span class="post-title" title="👍TestNG一篇足以">👍TestNG一篇足以</span>
            <span class="post-date" title="2020-08-22 18:37:28">2020/08/22</span>
        </a>
        
        <a  class="db mysql "
           href="/blog/2020/08/19/mysql-common-sql/"
           data-tag="mysql"
           data-author="沐雨云楼" >
            <span class="post-title" title="mysql常用sql">mysql常用sql</span>
            <span class="post-date" title="2020-08-19 21:30:00">2020/08/19</span>
        </a>
        
        <a  class="db mysql "
           href="/blog/2020/08/19/mysql-windows-zip-install/"
           data-tag="mysql"
           data-author="沐雨云楼" >
            <span class="post-title" title="mysql zip在windows上安装">mysql zip在windows上安装</span>
            <span class="post-date" title="2020-08-19 21:00:47">2020/08/19</span>
        </a>
        
        <a  class="工具 idea "
           href="/blog/2020/08/15/jetbrains-crack/"
           data-tag="工具,idea"
           data-author="沐雨云楼" >
            <span class="post-title" title="jetbrains全家桶破解">jetbrains全家桶破解</span>
            <span class="post-date" title="2020-08-15 19:22:33">2020/08/15</span>
        </a>
        
        <a  class="工具 git "
           href="/blog/2020/07/10/tool-git-error-name-too-long/"
           data-tag="git"
           data-author="沐雨云楼" >
            <span class="post-title" title="git文件名太长">git文件名太长</span>
            <span class="post-date" title="2020-07-10 12:03:02">2020/07/10</span>
        </a>
        
        <a  class="db mysql "
           href="/blog/2020/07/04/mysql-lock-unlock-table/"
           data-tag="lock"
           data-author="沐雨云楼" >
            <span class="post-title" title="mysql数据库锁查询和释放">mysql数据库锁查询和释放</span>
            <span class="post-date" title="2020-07-04 21:46:54">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-sort/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法8-排序">数据结构和算法8-排序</span>
            <span class="post-date" title="2020-07-04 18:49:12">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-search/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法7-搜索">数据结构和算法7-搜索</span>
            <span class="post-date" title="2020-07-04 17:48:19">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-graph/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法6-非线性-图">数据结构和算法6-非线性-图</span>
            <span class="post-date" title="2020-07-04 16:09:47">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-tree/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法5-非线性-树">数据结构和算法5-非线性-树</span>
            <span class="post-date" title="2020-07-04 15:09:47">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-linear-queue/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法4-线性-队列">数据结构和算法4-线性-队列</span>
            <span class="post-date" title="2020-07-04 14:10:22">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-linear-stack/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法3-线性-栈">数据结构和算法3-线性-栈</span>
            <span class="post-date" title="2020-07-04 13:00:17">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-linear-list/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法2-线性-链">数据结构和算法2-线性-链</span>
            <span class="post-date" title="2020-07-04 11:32:12">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-info/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法1-介绍">数据结构和算法1-介绍</span>
            <span class="post-date" title="2020-07-04 10:10:40">2020/07/04</span>
        </a>
        
        <a  class="大数据 spark "
           href="/blog/2020/06/30/spark-install-windows/"
           data-tag="spark"
           data-author="沐雨云楼" >
            <span class="post-title" title="spark开发环境搭建">spark开发环境搭建</span>
            <span class="post-date" title="2020-06-30 19:24:51">2020/06/30</span>
        </a>
        
        <a  class="大数据 hadoop "
           href="/blog/2020/06/30/hadoop-install-windows/"
           data-tag="hadoop"
           data-author="沐雨云楼" >
            <span class="post-title" title="hadoop开发环境搭建">hadoop开发环境搭建</span>
            <span class="post-date" title="2020-06-30 18:06:23">2020/06/30</span>
        </a>
        
        <a  class="java "
           href="/blog/2020/06/30/java-install-windows/"
           data-tag="java"
           data-author="沐雨云楼" >
            <span class="post-title" title="jdk开发环境搭建">jdk开发环境搭建</span>
            <span class="post-date" title="2020-06-30 15:09:34">2020/06/30</span>
        </a>
        
        <a  class="ai "
           href="/blog/2020/06/30/ai-python-spark-env/"
           data-tag="spark"
           data-author="沐雨云楼" >
            <span class="post-title" title="python spark开发环境搭建">python spark开发环境搭建</span>
            <span class="post-date" title="2020-06-30 12:14:04">2020/06/30</span>
        </a>
        
        <a  class="ai "
           href="/blog/2020/06/29/ai-jupyter-notebook/"
           data-tag="标签"
           data-author="沐雨云楼" >
            <span class="post-title" title="jupyter notebook">jupyter notebook</span>
            <span class="post-date" title="2020-06-29 12:29:36">2020/06/29</span>
        </a>
        
        <a  class="ai "
           href="/blog/2020/06/26/ai-python-tools/"
           data-tag="tools"
           data-author="沐雨云楼" >
            <span class="post-title" title="python和ai常用工具">python和ai常用工具</span>
            <span class="post-date" title="2020-06-26 09:55:24">2020/06/26</span>
        </a>
        
        <a  class="python "
           href="/blog/2020/06/25/python-tool-buildin-attr/"
           data-tag="attr"
           data-author="沐雨云楼" >
            <span class="post-title" title="👍python内置属性(魔法方法)">👍python内置属性(魔法方法)</span>
            <span class="post-date" title="2020-06-25 11:01:33">2020/06/25</span>
        </a>
        
        <a  class="python "
           href="/blog/2020/06/24/python-tool-buildin-func/"
           data-tag="func"
           data-author="沐雨云楼" >
            <span class="post-title" title="👍python内置函数">👍python内置函数</span>
            <span class="post-date" title="2020-06-24 18:31:59">2020/06/24</span>
        </a>
        
        <a  class="python "
           href="/blog/2020/06/24/python-tool-obj-dict/"
           data-tag="dict"
           data-author="沐雨云楼" >
            <span class="post-title" title="python对象与dict互转">python对象与dict互转</span>
            <span class="post-date" title="2020-06-24 18:15:03">2020/06/24</span>
        </a>
        
        <a  class="大数据 spark "
           href="/blog/2020/06/21/spark-version-3/"
           data-tag="spark"
           data-author="沐雨云楼" >
            <span class="post-title" title="spark3.0新特性">spark3.0新特性</span>
            <span class="post-date" title="2020-06-21 17:40:12">2020/06/21</span>
        </a>
        
        <a  class="java "
           href="/blog/2020/06/21/java-base-domain/"
           data-tag="domain"
           data-author="沐雨云楼" >
            <span class="post-title" title="VO DTO DO PO你都了解吗?">VO DTO DO PO你都了解吗?</span>
            <span class="post-date" title="2020-06-21 09:20:03">2020/06/21</span>
        </a>
        
        <a  class="大数据 spark "
           href="/blog/2020/06/20/spark-data-skew/"
           data-tag="spark"
           data-author="沐雨云楼" >
            <span class="post-title" title="spark数据倾斜及解决方案">spark数据倾斜及解决方案</span>
            <span class="post-date" title="2020-06-20 21:41:12">2020/06/20</span>
        </a>
        
        <a  class="linux nginx "
           href="/blog/2020/06/20/nginx-fast/"
           data-tag="nginx"
           data-author="沐雨云楼" >
            <span class="post-title" title="nginx为何这么快?">nginx为何这么快?</span>
            <span class="post-date" title="2020-06-20 17:55:10">2020/06/20</span>
        </a>
        
        <a  class="架构 "
           href="/blog/2020/06/20/fw-mq-message-missing/"
           data-tag="mq"
           data-author="沐雨云楼" >
            <span class="post-title" title="MQ如何保证消息不丢失?">MQ如何保证消息不丢失?</span>
            <span class="post-date" title="2020-06-20 17:03:18">2020/06/20</span>
        </a>
        
        <a  class="java "
           href="/blog/2020/06/20/java-base-serializable/"
           data-tag="序列化"
           data-author="沐雨云楼" >
            <span class="post-title" title="java序列化">java序列化</span>
            <span class="post-date" title="2020-06-20 16:29:04">2020/06/20</span>
        </a>
        
        <a  class="架构 "
           href="/blog/2020/06/20/fw-distributed-lock-redis-zk/"
           data-tag="lock,redis,zookeeper"
           data-author="沐雨云楼" >
            <span class="post-title" title="分布式锁用redis还是zk?">分布式锁用redis还是zk?</span>
            <span class="post-date" title="2020-06-20 12:09:55">2020/06/20</span>
        </a>
        
        <a  class="java tools "
           href="/blog/2020/06/19/java-tool-jackson/"
           data-tag="jackson"
           data-author="沐雨云楼" >
            <span class="post-title" title="工具类--jackson">工具类--jackson</span>
            <span class="post-date" title="2020-06-19 13:00:45">2020/06/19</span>
        </a>
        
        <a  class="java tools "
           href="/blog/2020/06/19/java-tool-bean-map/"
           data-tag="beanmap"
           data-author="沐雨云楼" >
            <span class="post-title" title="工具类--bean和map互转">工具类--bean和map互转</span>
            <span class="post-date" title="2020-06-19 12:30:14">2020/06/19</span>
        </a>
        
        <a  class="java test "
           href="/blog/2020/06/18/java-rest-assured-in-action/"
           data-tag="rest"
           data-author="沐雨云楼" >
            <span class="post-title" title="rest-assured实战">rest-assured实战</span>
            <span class="post-date" title="2020-06-18 17:51:56">2020/06/18</span>
        </a>
        
        <a  class="java test "
           href="/blog/2020/06/17/java_rest_assured_wiki_info/"
           data-tag="rest"
           data-author="沐雨云楼" >
            <span class="post-title" title="rest-assured wiki翻译">rest-assured wiki翻译</span>
            <span class="post-date" title="2020-06-17 20:39:11">2020/06/17</span>
        </a>
        
        <a  class="python tornado "
           href="/blog/2020/06/16/tornado-wtforms/"
           data-tag="wtforms"
           data-author="沐雨云楼" >
            <span class="post-title" title="wtforms表单验证">wtforms表单验证</span>
            <span class="post-date" title="2020-06-16 21:52:33">2020/06/16</span>
        </a>
        
        <a  class="python tornado "
           href="/blog/2020/06/16/tornado-sync-to-async/"
           data-tag="aysnc"
           data-author="沐雨云楼" >
            <span class="post-title" title="tornado同步转异步">tornado同步转异步</span>
            <span class="post-date" title="2020-06-16 21:50:25">2020/06/16</span>
        </a>
        
        <a  class="python tornado "
           href="/blog/2020/06/08/python_tornado_info/"
           data-tag="tornado"
           data-author="沐雨云楼" >
            <span class="post-title" title="👍Tornado入门这一篇足以">👍Tornado入门这一篇足以</span>
            <span class="post-date" title="2020-06-08 20:31:32">2020/06/08</span>
        </a>
        
        <a  class="工具 maven "
           href="/blog/2020/06/07/tool-maven/"
           data-tag="tools,工具"
           data-author="沐雨云楼" >
            <span class="post-title" title="maven常用命令和配置">maven常用命令和配置</span>
            <span class="post-date" title="2020-06-07 16:30:11">2020/06/07</span>
        </a>
        
        <a  class="微服务 springboot "
           href="/blog/2020/06/07/spring-initialzr/"
           data-tag="tools,工具"
           data-author="沐雨云楼" >
            <span class="post-title" title="spring initialzr环境编译发布">spring initialzr环境编译发布</span>
            <span class="post-date" title="2020-06-07 15:06:00">2020/06/07</span>
        </a>
        
        <a  class="windows "
           href="/blog/2020/06/07/windows-cmd/"
           data-tag="tools,工具,命令"
           data-author="沐雨云楼" >
            <span class="post-title" title="windows常用命令和技巧">windows常用命令和技巧</span>
            <span class="post-date" title="2020-06-07 11:39:01">2020/06/07</span>
        </a>
        
        <a  class="工具 github "
           href="/blog/2020/06/07/tool-connect-github/"
           data-tag="github"
           data-author="沐雨云楼" >
            <span class="post-title" title="github无法访问解决办法">github无法访问解决办法</span>
            <span class="post-date" title="2020-06-07 10:08:38">2020/06/07</span>
        </a>
        
        <a  class="微服务 spring "
           href="/blog/2020/06/03/spring-transaction/"
           data-tag="transactional"
           data-author="沐雨云楼" >
            <span class="post-title" title="Transactional注解">Transactional注解</span>
            <span class="post-date" title="2020-06-03 22:09:42">2020/06/03</span>
        </a>
        
        <a  class="java dao "
           href="/blog/2020/06/03/java-jpa-query-multi-param/"
           data-tag="JPA"
           data-author="沐雨云楼" >
            <span class="post-title" title="JPA多条件查询">JPA多条件查询</span>
            <span class="post-date" title="2020-06-03 21:38:04">2020/06/03</span>
        </a>
        
        <a  class="java tools "
           href="/blog/2020/06/02/java-tool-fastjson-bug/"
           data-tag="fastjson"
           data-author="沐雨云楼" >
            <span class="post-title" title="Fastjson远程代码高危漏洞">Fastjson远程代码高危漏洞</span>
            <span class="post-date" title="2020-06-02 22:38:28">2020/06/02</span>
        </a>
        
        <a  class="linux docker "
           href="/blog/2020/06/02/docker-introduction/"
           data-tag="docker"
           data-author="沐雨云楼" >
            <span class="post-title" title="👍docker入门看这一篇就够了">👍docker入门看这一篇就够了</span>
            <span class="post-date" title="2020-06-02 22:22:30">2020/06/02</span>
        </a>
        
        <a  class="面试 "
           href="/blog/2020/06/02/interview-java-question/"
           data-tag="面试"
           data-author="沐雨云楼" >
            <span class="post-title" title="java常见面试题">java常见面试题</span>
            <span class="post-date" title="2020-06-02 22:15:48">2020/06/02</span>
        </a>
        
        <a  class="微服务 "
           href="/blog/2020/06/02/microservice-why/"
           data-tag="微服务"
           data-author="沐雨云楼" >
            <span class="post-title" title="牛逼公司一定要使用微服务？">牛逼公司一定要使用微服务？</span>
            <span class="post-date" title="2020-06-02 21:15:29">2020/06/02</span>
        </a>
        
        <a  class="面试 "
           href="/blog/2020/06/02/interview-company/"
           data-tag="面试"
           data-author="沐雨云楼" >
            <span class="post-title" title="IT互联网公司名单">IT互联网公司名单</span>
            <span class="post-date" title="2020-06-02 20:41:23">2020/06/02</span>
        </a>
        
        <a  class="java 并发 "
           href="/blog/2020/06/02/java-concurrent-aqs/"
           data-tag="java,并发"
           data-author="沐雨云楼" >
            <span class="post-title" title="java并发AQS">java并发AQS</span>
            <span class="post-date" title="2020-06-02 20:01:48">2020/06/02</span>
        </a>
        
        <a  class="ai "
           href="/blog/2020/05/30/ai-learn-catalog/"
           data-tag="ai"
           data-author="沐雨云楼" >
            <span class="post-title" title="AI学习目录">AI学习目录</span>
            <span class="post-date" title="2020-05-30 08:49:39">2020/05/30</span>
        </a>
        
        <a  class="工具 hexo "
           href="/blog/2020/05/29/hexo-theme-math/"
           data-tag="工具,hexo"
           data-author="沐雨云楼" >
            <span class="post-title" title="hexo主题支持MathJax">hexo主题支持MathJax</span>
            <span class="post-date" title="2020-05-29 09:36:46">2020/05/29</span>
        </a>
        
        <a  class="db redis "
           href="/blog/2020/05/28/redis-memory-eliminate/"
           data-tag="redis"
           data-author="沐雨云楼" >
            <span class="post-title" title="Redis的内存淘汰策略">Redis的内存淘汰策略</span>
            <span class="post-date" title="2020-05-28 21:37:04">2020/05/28</span>
        </a>
        
        <a  class="工具 markdowm "
           href="/blog/2020/05/28/markdown-math-express/"
           data-tag="工具,markdowm"
           data-author="沐雨云楼" >
            <span class="post-title" title="markdown数学公式">markdown数学公式</span>
            <span class="post-date" title="2020-05-28 08:02:03">2020/05/28</span>
        </a>
        
        <a  class="python "
           href="/blog/2020/05/21/python_install/"
           data-tag="python"
           data-author="沐雨云楼" >
            <span class="post-title" title="python环境安装">python环境安装</span>
            <span class="post-date" title="2020-05-21 21:37:04">2020/05/21</span>
        </a>
        
        <a  class="python "
           href="/blog/2020/05/21/python_base/"
           data-tag="python"
           data-author="沐雨云楼" >
            <span class="post-title" title="python基本语法">python基本语法</span>
            <span class="post-date" title="2020-05-21 00:00:00">2020/05/21</span>
        </a>
        
        <a  class="其他 "
           href="/blog/2020/05/20/todo-list/"
           data-tag="plan,计划"
           data-author="沐雨云楼" >
            <span class="post-title" title="计划">计划</span>
            <span class="post-date" title="2020-05-20 11:04:19">2020/05/20</span>
        </a>
        
        <a  class="工具 "
           href="/blog/2020/05/20/blog-template/"
           data-tag="模板"
           data-author="沐雨云楼" >
            <span class="post-title" title="博客自定义模板">博客自定义模板</span>
            <span class="post-date" title="2020-05-20 05:20:00">2020/05/20</span>
        </a>
        
    </nav>
</div>

    </div>
    <div class="hide-list">
        <div class="semicircle" data-title="切换全屏 快捷键 s">
            <div class="brackets first"><</div>
            <div class="brackets">&gt;</div>
        </div>
    </div>
</aside>
<div class="post">
    <div class="pjax">
        <article id="post-data-structures-algorithms-tree" class="article article-type-post" itemscope itemprop="blogPost">
    
        <h1 class="article-title">数据结构和算法5-非线性-树</h1>
    
    <div class="article-meta">
        
        
        <span class="author"><a>沐雨云楼</a></span>
        
        
        <span class="book">
            
                <a  data-rel="结构和算法">结构和算法</a>
            
        </span>
        
        
        <span class="tag">
            
            <a class="color1">结构和算法</a>
            
        </span>
        
    </div>
    <div class="article-meta">
        
            发布时间 : <time class="date" title='最后更新: 2020-09-12 21:21:47'>2020-07-04 15:09</time>
        
    </div>
    <div class="article-meta">
        
        <span>字数:6.2k</span>
        
        
        <span id="busuanzi_container_page_pv">
            阅读 :<span id="busuanzi_value_page_pv">
                <span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </span>
        </span>
        
        
        <span class="top-comment" title="跳转至评论区">
            <a href="#comments">
                评论:<span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </a>
        </span>
        
    </div>
    
    <div class="toc-ref">
    
        <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#1-概念"><span class="toc-text">1.概念</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-1-什么是树"><span class="toc-text">1-1.什么是树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-2-度"><span class="toc-text">1-2.度</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-3-深度"><span class="toc-text">1-3.深度</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-树的分类"><span class="toc-text">1-4.树的分类</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-5-节点间关系"><span class="toc-text">1-5.节点间关系</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-二叉树"><span class="toc-text">2.二叉树</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#2-1-二叉树特性"><span class="toc-text">2-1.二叉树特性</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-2-二叉树分类"><span class="toc-text">2-2.二叉树分类</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#2-2-1-满二叉树"><span class="toc-text">2-2-1.满二叉树</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2-2-2-完全二叉树"><span class="toc-text">2-2-2.完全二叉树</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-3-二叉树的存储结构"><span class="toc-text">2-3.二叉树的存储结构</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#2-3-1-顺序数组存储"><span class="toc-text">2-3-1.顺序数组存储</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2-3-2-链结构存储"><span class="toc-text">2-3-2.链结构存储</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-遍历"><span class="toc-text">3.遍历</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-前序遍历"><span class="toc-text">3-1.前序遍历</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-2-中序遍历"><span class="toc-text">3-2.中序遍历</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-3-后序遍历"><span class="toc-text">3-3.后序遍历</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#4-代码实战"><span class="toc-text">4.代码实战</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#4-1-接口"><span class="toc-text">4-1.接口</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-2-实现代码"><span class="toc-text">4-2.实现代码</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#4-2-1-空判断"><span class="toc-text">4-2-1.空判断</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4-2-2-大小"><span class="toc-text">4-2-2.大小</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4-2-3-树深度"><span class="toc-text">4-2-3.树深度</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4-2-4-查找"><span class="toc-text">4-2-4.查找</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4-2-5-前序遍历"><span class="toc-text">4-2-5.前序遍历</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4-2-6-中序遍历"><span class="toc-text">4-2-6.中序遍历</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4-2-7-后序遍历"><span class="toc-text">4-2-7.后序遍历</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4-2-8-水平遍历"><span class="toc-text">4-2-8.水平遍历</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-3-整体代码"><span class="toc-text">4-3.整体代码</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-4-测试代码"><span class="toc-text">4-4.测试代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#5-链接"><span class="toc-text">5.链接</span></a></li></ol>
    
<style>
    .left-col .switch-btn,
    .left-col .switch-area {
        display: none;
    }
    .toc-level-4 i,
    .toc-level-4 ol {
        display: none !important;
    }
</style>
</div>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>先介绍个工具</p>
<ul>
<li><a href="https://www.cs.usfca.edu/~galles/visualization/Algorithms.html" target="_blank" rel="noopener">数据结构在线动画工具</a></li>
</ul>
<h2 id="1-概念"><a href="#1-概念" class="headerlink" title="1.概念"></a>1.概念</h2><h3 id="1-1-什么是树"><a href="#1-1-什么是树" class="headerlink" title="1-1.什么是树"></a>1-1.什么是树</h3><p>树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。<br>没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。</p>
<img src="/blog/images/da/da-tree-simple.png" width="200px">

<h3 id="1-2-度"><a href="#1-2-度" class="headerlink" title="1-2.度"></a>1-2.度</h3><p>度(degree)分为</p>
<ul>
<li>节点的度, 含有几个子节点(儿子)<ul>
<li>degree为0的节点，称为叶子节点leaf</li>
<li>最上层的曾为根节点root</li>
<li>degree不为0的节点，除根以外称为内部节点</li>
</ul>
</li>
<li>树的度，各节点的最大degree称为树的degree (m叉树)</li>
</ul>
<img src="/blog/images/da/da-tree-degree.png" width="450px">

<h3 id="1-3-深度"><a href="#1-3-深度" class="headerlink" title="1-3.深度"></a>1-3.深度</h3><p>深度(depth)又叫层次(level),root为第一层，其子节点为第二层，子的子为第三层…以此类推</p>
<img src="/blog/images/da/da-tree-level.png" width="450px">

<h3 id="1-4-树的分类"><a href="#1-4-树的分类" class="headerlink" title="1-4.树的分类"></a>1-4.树的分类</h3><p><strong>顺序分</strong></p>
<p>如果树的节点是有顺序的，那就是有序树，没有顺序的则是无序的</p>
<p><strong>节点分</strong></p>
<p>按树所有node里，某node的子node最多树为m，那就是m叉树 (以最多的为基准，即树的degree)</p>
<p><strong>树的个数分</strong></p>
<p>多棵树组成一个森林，一个树只是特殊的森林。</p>
<h3 id="1-5-节点间关系"><a href="#1-5-节点间关系" class="headerlink" title="1-5.节点间关系"></a>1-5.节点间关系</h3><p><strong>直接关系</strong></p>
<ul>
<li>父节点：一个节点直接前节点</li>
<li>子节点：一个节点直接后节点</li>
<li>兄弟节点：同一父节点的，其他节点</li>
</ul>
<p><strong>间接关系</strong></p>
<ul>
<li>祖先：从根到该节点所经分支上的所有节点；</li>
<li>子孙：以某节点为根的子树中任一节点都称为该节点的子孙。</li>
<li>堂兄弟节点：双亲在同一层的节点互为堂兄弟</li>
</ul>
<img src="/blog/images/da/da-tree-relationship.jpeg" width="650px">


<h2 id="2-二叉树"><a href="#2-二叉树" class="headerlink" title="2.二叉树"></a>2.二叉树</h2><p>二叉树，是m叉树为2的特殊树(即:树的degree小于等于2)。</p>
<h3 id="2-1-二叉树特性"><a href="#2-1-二叉树特性" class="headerlink" title="2-1.二叉树特性"></a>2-1.二叉树特性</h3><img src="/blog/images/da/da-btree-feature.png" width="750px">


<p><strong>有兴趣的可以看下其证明</strong></p>
<ul>
<li><a href="https://blog.csdn.net/jun2016425/article/details/54581407" target="_blank" rel="noopener">二叉树特性及证明1</a></li>
<li><a href="https://blog.csdn.net/qq_41795143/article/details/103292676" target="_blank" rel="noopener">二叉树性质及证明2</a></li>
</ul>
<h3 id="2-2-二叉树分类"><a href="#2-2-二叉树分类" class="headerlink" title="2-2.二叉树分类"></a>2-2.二叉树分类</h3><h4 id="2-2-1-满二叉树"><a href="#2-2-1-满二叉树" class="headerlink" title="2-2-1.满二叉树"></a>2-2-1.满二叉树</h4><p>高度为k并且有$2^{k+1}-1$个结点的二叉树。</p>
<img src="/blog/images/da/da-btree-all.png" width="350px">


<h4 id="2-2-2-完全二叉树"><a href="#2-2-2-完全二叉树" class="headerlink" title="2-2-2.完全二叉树"></a>2-2-2.完全二叉树</h4><p>基于满二叉树，在最下层从最右侧起去掉相邻的若干叶子结点，得到的二叉树称为完全二叉树。</p>
<img src="/blog/images/da/da-btree-prefect.png" width="350px">


<h3 id="2-3-二叉树的存储结构"><a href="#2-3-二叉树的存储结构" class="headerlink" title="2-3.二叉树的存储结构"></a>2-3.二叉树的存储结构</h3><ul>
<li>顺序数组存储</li>
<li>链结构存储</li>
</ul>
<h4 id="2-3-1-顺序数组存储"><a href="#2-3-1-顺序数组存储" class="headerlink" title="2-3-1.顺序数组存储"></a>2-3-1.顺序数组存储</h4><p>如果是完全二叉树，用顺序存储很好。但是不是完全二叉树的话，中间会有空留，占用空间。</p>
<img src="/blog/images/da/da-btree-store-array-all-perfect.png" width="550px">

<img src="/blog/images/da/da-btree-store-array-single.png" width="550px">

<h4 id="2-3-2-链结构存储"><a href="#2-3-2-链结构存储" class="headerlink" title="2-3-2.链结构存储"></a>2-3-2.链结构存储</h4><p>链表结构比较适合二叉树存储。node节点结构：<strong>左子节点、数据、右子节点</strong>。</p>
<blockquote>
<p>这样的数据结构，只能保证父找到子，不能保证子找父的。(如需子找到父，那还得需要多加个父节点存储)</p>
</blockquote>
<img src="/blog/images/da/da-btree-store-list.png" width="850px">

<h2 id="3-遍历"><a href="#3-遍历" class="headerlink" title="3.遍历"></a>3.遍历</h2><p>二叉树遍历根据root的位置分三种</p>
<ul>
<li>前序遍历：根-左-右 DLR</li>
<li>中序遍历：左-根-右 LDR</li>
<li>后序遍历：左-右-根 LRD</li>
</ul>
<img src="/blog/images/da/da-btree-foreach.png" width="850px" height="400px">

<h3 id="3-1-前序遍历"><a href="#3-1-前序遍历" class="headerlink" title="3-1.前序遍历"></a>3-1.前序遍历</h3><p><strong>心法口诀：首先访问根，再先序遍历左子树，最后先序遍历右子树</strong></p>
<img src="/blog/images/da/da-btree-foreach-example.png" width="450px">

<p><strong>传统分析</strong></p>
<blockquote>
<p>1.找到root-1，然后左边子node-4，右边子node-1。得到<code>1 4_ 2_</code><br>2.再分析左边的node-4，node-4的左子node没有，右子node为node-5。得到<code>1 4 5 2_</code><br>3.左边没有，在分析右边node-2，node-2的左子node-3，右子node-6。得到<code>1 4 5 2 3 6 _</code><br>4.再分析node-3的，左右子node都没有，是leaf<br>5.再分析node-6，左子node没有，右子node-7。得到<code>1 4 5 2 3 6 7</code></p>
</blockquote>
<p><strong>个人技巧</strong></p>
<img src="/blog/images/da/da-btree-foreach-pre.png" width="450px">

<blockquote>
<p>注意上面箭头方向。从最左上，每次一层，所得的结果就是前序结果。</p>
</blockquote>
<p>用咱的小技巧去试试前面的二叉树吧，看是不是得到一样的结果。</p>
<h3 id="3-2-中序遍历"><a href="#3-2-中序遍历" class="headerlink" title="3-2.中序遍历"></a>3-2.中序遍历</h3><p><strong>心法口诀：首先中序遍历左子树，再访问根，最后中序遍历右子树</strong></p>
<img src="/blog/images/da/da-btree-foreach-example.png" width="450px">

<p><strong>传统分析</strong></p>
<blockquote>
<p>1.找到root-1放中间，然后左边子node-4放左侧，右边子node-1放右侧。得到<code>_4_ 1 2_</code>(此时下划线是4和2的)<br>2.再分析左边的node-4，node-4的左子node没有，右子node为node-5。得到<code>4 5 1 _2_</code>(此时下划线是2的)<br>3.左边没有，在分析右边node-2，node-2的左子node-3放左侧，右子node-6放右测。得到<code>4 5 1 _3_2_6_</code>(此时下划线是3和6的)<br>4.再分析node-3的，左右子node都没有，是leaf。<code>4 5 1 3 2_6_</code>(3没有左右，那么就将3的左右下划线删去)<br>5.再分析node-6，左子node没有，右子node-7放右测。得到<code>4 5 1 3 2 6 7</code></p>
</blockquote>
<p><strong>个人技巧</strong></p>
<img src="/blog/images/da/da-btree-foreach-in.png" width="450px">

<blockquote>
<p>因为根在中间，那不就是跟我们二叉树一样吗!!!(左根右，LDR)，所以直接把二叉树压平到一条线，不就是需要的顺序吗? 是不是so easy😀!<br>我相信你看到这，肯定想将文章拉到最后，要给我一个大大的赞👍或者来段评论啥的(去吧，不拦你😄，记得回来找我，接着往下看)。</p>
</blockquote>
<p>用咱的小技巧去试试前面的二叉树吧，看是不是得到一样的结果。</p>
<h3 id="3-3-后序遍历"><a href="#3-3-后序遍历" class="headerlink" title="3-3.后序遍历"></a>3-3.后序遍历</h3><p><strong>心法口诀：首先中序遍历左子树，再中序遍历右子树，最后访问根</strong></p>
<img src="/blog/images/da/da-btree-foreach-example.png" width="450px">

<p><strong>传统分析</strong></p>
<blockquote>
<p>1.找到root-1放最后，然后左边子node-4放左1侧，右边子node-1放左2侧。得到<code>_4 _2 1</code>(此时下划线是4和2的)<br>2.再分析左边的node-4，node-4的左子node没有，右子node为node-5放左2侧。得到<code>5 4 _2 1</code>(此时下划线是2的)<br>3.左边没有，在分析右边node-2，node-2的左子node-3放左1侧，右子node-6放左2测。得到<code>5 4 _3 _6 2 1</code>(此时下划线是3和6的)<br>4.再分析node-3的，左右子node都没有，是leaf。<code>5 4 3 _6 2 1</code>(3没有左右，那么就将3的左右下划线删去)<br>5.再分析node-6，左子node没有，右子node-7放左2侧。得到<code>5 4 3 7 6 2 1</code></p>
</blockquote>
<p><strong>个人技巧</strong></p>
 <img src="/blog/images/da/da-btree-foreach-post_complex.png" width="550px">

<p>这个小技巧没上面个两种直观。但也能出来，比较啰嗦。说下，能理解的就用，不理解的话，还是使用传统方式</p>
<blockquote>
<p>口诀：由左到右,由下往上的顺序(左的优先级比下高)。先左看再右看最后向前看齐(跟<strong>中国式过马路似的</strong>，先左再右看，最后前看。下面右解释)，每遇到root有分叉，将root放局部最后位置。(因为是后序遍历，所以遇到是root的，直接放到局部域最后位置)</p>
<ol>
<li>6虽比9层次低，但是6比9靠左，左的优先级比下高。6开始，往上找祖先，直到遇到4分叉了。<strong>先左看再右看，最后向前看</strong>。将2放局部最后。结果为：<code>7 6 4 _ 2</code> (此时下划线是2的)</li>
<li>继续找左分支上，最左且最下层没有处理过的node为9。往上走找祖先，直到2没遇到分叉。结果为：<code>7 6 4 9 8 5 2</code></li>
<li>2继续找祖先,遇到了1分支。将1放局部最后。结果为：<code>7 6 4 9 8 5 2 _ 1</code> (此时下划线是1的，代表1右节点遍历数据)</li>
<li>看右测的最左且最下层是10，往上找祖先，直到遇到1分叉。结果为：<code>7 6 4 9 8 5 2 10 12 11 3 1</code> </li>
</ol>
</blockquote>
<p><strong>这有几点说明：</strong></p>
<ul>
<li><strong>左的优先级比下高</strong>：6虽比9层次低，但是6比9靠左，左的优先级比下高。（虽然9在第5层，6和4在第4和3层）。因为左比层次(下)优先级高。</li>
<li><strong>先左看再右看，最后向前看</strong>：意思6是4的左节点，7在4的右子节点上。那是先6再7最后4的顺序。</li>
</ul>
<p><strong>说下马路过程：(大家都知道中国交通规则是靠右行的)，直接上图吧</strong></p>
<img src="/blog/images/da/da-btree-pass-road.png" width="550px">

<blockquote>
<p>1.过马路，还没过一半前，<strong>先左边看</strong>，因为汽车是靠右行的，防止有车冲过来。<br>2.过完一半后，<strong>再左边看</strong>，防止另一半车再冲过来<br>3.过完马路了，左右都安全了，<strong>最后往前看</strong>走路</p>
</blockquote>
<h2 id="4-代码实战"><a href="#4-代码实战" class="headerlink" title="4.代码实战"></a>4.代码实战</h2><h3 id="4-1-接口"><a href="#4-1-接口" class="headerlink" title="4-1.接口"></a>4-1.接口</h3><p><strong>接口</strong></p>
<pre><code class="java">public interface ITree {
    /**
     * 是否空树
     *
     * @return
     */
    public boolean isEmpty();

    /**
     * 树结点数量
     *
     * @return
     */
    public int size();

    /**
     * 获取二叉树的高度
     *
     * @return
     */
    public int getHeight();

    /**
     * 查询指定值的结点
     *
     * @param value
     * @return
     */
    public TreeNode findKey(int value); // 查找

    /**
     * 前序递归遍历
     */
    public void preOrderTraverse();

    /**
     * 中序遍历递归操作
     */
    public void inOrderTraverse();

    /**
     * 后序遍历递归操作
     */
    public void postOrderTraverse();

    /**
     * 中序遍历非递归操作
     * 1）对于任意节点current，若该节点不为空则将该节点压栈，并将左子树节点置为current，重复此操作，直到current为空。
     * 2）若左子树为空，栈顶节点出栈，访问节点后将该节点的右子树置为current
     * 3) 重复1、2步操作，直到current为空且栈内节点为空。
     */
    public void inOrderByStack();

    /**
     * 前序遍历非递归操作
     * 1）对于任意节点current，若该节点不为空则访问该节点后再将节点压栈，并将左子树节点置为current，重复此操作，直到current为空。
     * 2）若左子树为空，栈顶节点出栈，将该节点的右子树置为current
     * 3) 重复1、2步操作，直到current为空且栈内节点为空。
     */
    public void preOrderByStack();

    /**
     * 后序遍历非递归操作
     * 1）对于任意节点current，若该节点不为空则访问该节点后再将节点压栈，并将左子树节点置为current，重复此操作，直到current为空。
     * 2）若左子树为空，取栈顶节点的右子树，如果右子树为空或右子树刚访问过，则访问该节点，并将preNode置为该节点
     * 3) 重复1、2步操作，直到current为空且栈内节点为空。
     */
    public void postOrderByStack();

    /**
     * 按照层次遍历二叉树
     */
    public void levelOrderByQueue();

}</code></pre>
<p><strong>二叉node节点定义</strong></p>
<pre><code class="java">public class TreeNode {

    private Object data;

    private TreeNode leftChild;

    private TreeNode rightChild;

    public TreeNode(Object data, TreeNode leftChild, TreeNode rightChild) {
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public TreeNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(TreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public TreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(TreeNode rightChild) {
        this.rightChild = rightChild;
    }

    @Override
    public String toString() {
        return &quot;TreeNode{&quot; + &quot;data=&quot; + data + &quot;, leftChild=&quot; + leftChild.getData() + &quot;, rightChild=&quot; + rightChild.getData() + &#39;}&#39;;
    }
}</code></pre>
<h3 id="4-2-实现代码"><a href="#4-2-实现代码" class="headerlink" title="4-2.实现代码"></a>4-2.实现代码</h3><p>整体实现代码最后整体给出，这先每个片段给出，并分析。</p>
<blockquote>
<p>分析尽我最大解释，实在不懂，那就得靠自己悟了</p>
</blockquote>
<h4 id="4-2-1-空判断"><a href="#4-2-1-空判断" class="headerlink" title="4-2-1.空判断"></a>4-2-1.空判断</h4><pre><code class="java">public class MyListBinaryTree implements ITree {

    private TreeNode root;

    public MyListBinaryTree(TreeNode root) {
        this.root = root;
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }
}</code></pre>
<blockquote>
<p>只要判断root是否为空</p>
</blockquote>
<h4 id="4-2-2-大小"><a href="#4-2-2-大小" class="headerlink" title="4-2-2.大小"></a>4-2-2.大小</h4><pre><code class="java">public int size() {
        return size(this.root);
    }

private int size(TreeNode node) {
    // 为null时返回0，不为null时加一
    if (node == null) {
        return 0;
    }
    int leftSize = size(node.getLeftChild());
    int rightSize = size(node.getRightChild());
    // 左右子节点都会掉一次，所以只要node为null的只要自己加一就行
    return leftSize + rightSize + 1;
}</code></pre>
<blockquote>
<p>使用递归方式，每次将left child和 right child传进去。空的时候，就返回0，否则加一</p>
</blockquote>
<h4 id="4-2-3-树深度"><a href="#4-2-3-树深度" class="headerlink" title="4-2-3.树深度"></a>4-2-3.树深度</h4><pre><code class="java">@Override
    public int getHeight() {
        // 求深度，即求从root出来的child node谁最长
        return getHeight(root);
    }

private int getHeight(TreeNode node) {
    if (node == null) {
        return 0;
    }
    // 左子节点
    int leftNum = getHeight(node.getLeftChild());

    // 右子节点
    int rightNum = getHeight(node.getLeftChild());

    // 返回大的+1
    return leftNum &gt; rightNum ? leftNum + 1 : rightNum + 1;
}</code></pre>
<blockquote>
<p>使用递归方式，每次将left child和 right child传进去。空的时候，就返回0，否则将左右返回值中较大的加一</p>
</blockquote>
<h4 id="4-2-4-查找"><a href="#4-2-4-查找" class="headerlink" title="4-2-4.查找"></a>4-2-4.查找</h4><pre><code class="java">@Override
    public TreeNode findKey(Object value) {
        return this.findKey(value, root);
    }

private TreeNode findKey(Object value, TreeNode node) {
    if (node == null) {
        return null;
    }

    if (node.getData().equals(value)) {
        return node;
    }

    TreeNode leftNode = findKey(value, node.getLeftChild());

    TreeNode rightNode = findKey(value, node.getRightChild());

    if (leftNode != null) {
        return leftNode;
    }

    if (rightNode != null) {
        return rightNode;
    }

    return null;
}</code></pre>
<blockquote>
<p>递归查找</p>
</blockquote>
<h4 id="4-2-5-前序遍历"><a href="#4-2-5-前序遍历" class="headerlink" title="4-2-5.前序遍历"></a>4-2-5.前序遍历</h4><p><strong>递归方式实现</strong></p>
<pre><code class="java">@Override
public void preOrderTraverse() {
    this.preOrderTraverse(root);
}

private void preOrderTraverse(TreeNode node) {
    if (node == null) {
        return;
    }
    // d输出
    System.out.print(node.getData() + &quot; &quot;);
    // l处理
    preOrderTraverse(node.getLeftChild());
    // r处理
    preOrderTraverse(node.getRightChild());
}</code></pre>
<img src="/blog/images/da/da-btree-foreach-complex-example.png" width="450px">

<blockquote>
<p>擦，不知从何讲起呀。(理解一眼就明白，不明白的，言语也解释不了😂)<br>递归：<br>1.给出终止条件，node为空结束<br>2.将根节点传给方法，因为前序遍历，所以要将d先输出<br>3.再将左子节点传给方法，作为根继续处理<br>4.将右子节点也传给递归方法，作为根继续处理</p>
</blockquote>
<p><strong>栈方式实现</strong></p>
<pre><code class="java">@Override
public void preOrderByStack() {
    Deque&lt;TreeNode&gt; stack = new LinkedList&lt;&gt;();
    if (root == null) {
        return;
    }

    // 心法：以当前node移动，根据DLR、LDR、LRD的顺序去如何存取到stack中去
    // 指向树的当前移动node点
    TreeNode current = root;
    List&lt;Object&gt; result = new ArrayList&lt;&gt;();
    while (current != null || !stack.isEmpty()) {
        // 将current node的所有左子节点全放到栈里，一致循环直到左子node为null
        while (current != null) {
            // 输出
            result.add(current.getData());
            stack.push(current);
            // 要移动current node的位置给current node (即left node)
            current = current.getLeftChild();
        }

        // 如果栈不为空，那就从栈中弹出栈顶元素
        // 将current node的right node给 current node，供下次循环找其所有的left node
        if (!stack.isEmpty()) {
            current = stack.pop();
            current = current.getRightChild();
        }
    }
    System.out.println(result);
}</code></pre>
<img src="/blog/images/da/da-btree-foreach-complex-example.png" width="450px">

<blockquote>
<p>上面代码有注释<br>大体思路:<br>从根起，将所有左节点全入栈中(从栈顶到栈尾为：6、4、2、1)，因为前序遍历，所以这时就要输出了，此时current为空跳出内部的while循环<br>到达if判断，从栈中弹出栈顶6，并赋值给current，并将6的右子节点7再赋给current（没有），此时4为栈顶。<br>循环一次while，将4弹出栈，将4右子节点给current，此时2成为栈顶了。<br>再做一次while循环，将7下面所有节点处理一边。发现没有，继续弹出2…(以此类推)</p>
</blockquote>
<h4 id="4-2-6-中序遍历"><a href="#4-2-6-中序遍历" class="headerlink" title="4-2-6.中序遍历"></a>4-2-6.中序遍历</h4><p><strong>递归方式实现</strong></p>
<pre><code class="java">@Override
public void inOrderTraverse() {
    this.inOrderTraverse(root);
}

private void inOrderTraverse(TreeNode node) {
    if (node == null) {
        return;
    }
    // l处理
    inOrderTraverse(node.getLeftChild());
    // d输出
    System.out.print(node.getData() + &quot; &quot;);
    // r处理
    inOrderTraverse(node.getRightChild());
}</code></pre>
<img src="/blog/images/da/da-btree-foreach-complex-example.png" width="450px">

<blockquote>
<p>递归：<br>1.给出终止条件，node为空结束<br>2.将根节点传给方法，因为中序遍历，所以要将d先放l和r中间</p>
</blockquote>
<p><strong>栈方式实现</strong></p>
<pre><code class="java">@Override
public void inOrderByStack() {
    Deque&lt;TreeNode&gt; stack = new LinkedList&lt;&gt;();
    if (root == null) {
        return;
    }

    // 心法：以当前node移动，根据DLR、LDR、LRD的顺序去如何存取到stack中去
    // 指向树的当前移动node点
    TreeNode current = root;
    List&lt;Object&gt; result = new ArrayList&lt;&gt;();
    while (current != null || !stack.isEmpty()) {
        // 将current node的所有左子节点全放到栈里，一致循环直到左子node为null
        while (current != null) {
            stack.push(current);
            // 要移动current node的位置给current node (即left node)
            current = current.getLeftChild();
        }

        // 如果栈不为空，那就从栈中弹出栈顶元素，输出
        // 将current node的right node给 current node，供下次循环找其所有的left node
        if (!stack.isEmpty()) {
            current = stack.pop();
            result.add(current.getData());
            current = current.getRightChild();
        }
    }
    System.out.println(result);
}</code></pre>
<img src="/blog/images/da/da-btree-foreach-complex-example.png" width="450px">

<blockquote>
<p>上面代码有注释<br>大体思路:<br>从根起，将所有左节点全入栈中(从栈顶到栈尾为：6、4、2、1)，此时current为空跳出内部的while循环<br>到达if判断，从栈中弹出栈顶6，并赋值给current，因为是中序遍历，所以弹栈时就要输出，再将6的右子节点给current（为null），此时4成为栈顶。<br>再做一次while循环,从栈中弹出栈顶4, 将4的右子节点7再赋给current, 此是2成为了栈顶<br>再做一次while循环，将7下面所有节点处理一边。发现没有，继续弹出2…(以此类推)</p>
</blockquote>
<h4 id="4-2-7-后序遍历"><a href="#4-2-7-后序遍历" class="headerlink" title="4-2-7.后序遍历"></a>4-2-7.后序遍历</h4><p><strong>递归方式实现</strong></p>
<pre><code class="java">@Override
public void postOrderTraverse() {
    this.postOrderTraverse(root);
}

private void postOrderTraverse(TreeNode node) {
    if (node == null) {
        return;
    }
    // l处理
    postOrderTraverse(node.getLeftChild());
    // r处理
    postOrderTraverse(node.getRightChild());
    // d输出
    System.out.print(node.getData() + &quot; &quot;);
}</code></pre>
<img src="/blog/images/da/da-btree-foreach-complex-example.png" width="450px">

<blockquote>
<p>递归：<br>1.给出终止条件，node为空结束<br>2.将根节点传给方法，因为中序遍历，所以要将d先放l和r后面</p>
</blockquote>
<p><strong>栈方式实现1</strong></p>
<pre><code class="java">@Override
public void postOrderByStack() {

    // 方式一：
    Deque&lt;TreeNode&gt; stack = new LinkedList&lt;&gt;();
    if (root == null) {
        return;
    }
    List&lt;Object&gt; result = new ArrayList&lt;&gt;();
    // 指向树的当前移动node点
    TreeNode current = null;
    // 指向当前移动node的其中一个子节点(即，栈上的上一个栈顶)
    TreeNode tmpChildNode = null;

    stack.push(root);
    while (!stack.isEmpty()) {
        current = stack.peek();
        if ((current.getLeftChild() == null &amp;&amp; current.getRightChild() == null) || current.getLeftChild() == tmpChildNode || current
                .getRightChild() == tmpChildNode) {
            result.add(current.getData());
            stack.pop();
            tmpChildNode = current;
        } else {
            // 先添加right child node ，因为栈是LIFO
            if (current.getRightChild() != null) {
                stack.push(current.getRightChild());
            }
            // 再添加left child node ，因为栈是LIFO
            if (current.getLeftChild() != null) {
                stack.push(current.getLeftChild());
            }
        }
    }
    System.out.println(result);
}</code></pre>
<img src="/blog/images/da/da-btree-foreach-complex-example.png" width="450px">

<blockquote>
<p>思想：<br>将节点压到栈中，然后通过栈顶元素去判断有没子节点，有则入栈，没有则出栈。<br>出栈时打印结果。注意打印的条件两个</p>
<ul>
<li>没有子节点，即leaf，需要打印</li>
<li>出栈的节点的有子节点，但是前一次出栈的节点，也需要打印</li>
</ul>
</blockquote>
<p><strong>栈方式实现2</strong></p>
<pre><code class="java"> @Override
public void postOrderByStack() {
    // 方式二
    Deque&lt;TreeNode&gt; stack = new LinkedList&lt;&gt;();
    if (root == null) {
        return;
    }

    // 心法：以当前node移动，根据DLR、LDR、LRD的顺序去如何存取到stack中去
    // 指向树的当前移动node点
    TreeNode current = root;
    List&lt;Object&gt; result = new ArrayList&lt;&gt;();
    while (current != null || !stack.isEmpty()) {
        // 将current node的所有右子节点全放到栈里，一致循环直到右子node为null
        while (current != null) {
            stack.push(current);
            // 要移动current node的位置给current node (即right node)
            result.add(current.getData());
            current = current.getRightChild();
        }

        // 如果栈不为空，那就从栈中弹出栈顶元素，输出
        // 将current node的left node给 current node，供下次循环找其所有的right node
        if (!stack.isEmpty()) {
            current = stack.pop();
            current = current.getLeftChild();
        }
    }
    // 反转下结果
    Collections.reverse(result);
    System.out.println(result);
}</code></pre>
<img src="/blog/images/da/da-btree-foreach-complex-example.png" width="450px">

<blockquote>
<p>思路：<br>此要放结合前序栈方式遍历来理解(前序栈方式，以左子节点为先，一直while循环压榨)，而这后序栈方式，以右为先进行压栈<br>不过最后结果饭的，需要反转一下</p>
</blockquote>
<h4 id="4-2-8-水平遍历"><a href="#4-2-8-水平遍历" class="headerlink" title="4-2-8.水平遍历"></a>4-2-8.水平遍历</h4><pre><code class="java">@Override
public void levelOrderByQueue() {
    Deque&lt;TreeNode&gt; queue = new LinkedList&lt;&gt;();
    if (root == null) {
        return;
    }
    List&lt;Object&gt; result = new ArrayList&lt;&gt;();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int len = queue.size();
        // 遍历将stack里元素弹出
        for (int i = 0; i &lt; len; i++) {
            TreeNode node = queue.poll();
            result.add(node.getData());
            TreeNode leftChild = node.getLeftChild();
            TreeNode rightChild = node.getRightChild();
            if (leftChild != null) {
                queue.offer(leftChild);
            }
            if (rightChild != null) {
                queue.offer(rightChild);
            }
        }
    }
    System.out.println(result);
}</code></pre>
<img src="/blog/images/da/da-btree-foreach-complex-example.png" width="450px">

<blockquote>
<p>水平遍历要借助队列的特性来处理，将每层的放进queue里队尾，从头取出(每次while加一层数据，需要取将queue里数据都取出)</p>
</blockquote>
<h3 id="4-3-整体代码"><a href="#4-3-整体代码" class="headerlink" title="4-3.整体代码"></a>4-3.整体代码</h3><pre><code class="java">package com.iworkh.da.lesson03;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 自定义二叉树
 *
 * @author: iworkh-沐雨云楼
 * @date: 2020-07-02
 */
public class MyListBinaryTree implements ITree {

    private TreeNode root;

    public MyListBinaryTree(TreeNode root) {
        this.root = root;
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }

    @Override
    public int size() {
        return size(this.root);
    }

    private int size(TreeNode node) {
        // 为null时返回0，不为null时加一
        if (node == null) {
            return 0;
        }
        int leftSize = size(node.getLeftChild());
        int rightSize = size(node.getRightChild());
        // 左右子节点都会掉一次，所以只要node为null的只要自己加一就行
        return leftSize + rightSize + 1;
    }

    @Override
    public int getHeight() {
        // 求深度，即求从root出来的child node谁最长
        return getHeight(root);
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 左子节点
        int leftNum = getHeight(node.getLeftChild());

        // 右子节点
        int rightNum = getHeight(node.getLeftChild());

        // 返回大的+1
        return leftNum &gt; rightNum ? leftNum + 1 : rightNum + 1;
    }

    @Override
    public TreeNode findKey(Object value) {
        return this.findKey(value, root);
    }

    private TreeNode findKey(Object value, TreeNode node) {
        if (node == null) {
            return null;
        }

        if (node.getData().equals(value)) {
            return node;
        }

        TreeNode leftNode = findKey(value, node.getLeftChild());

        TreeNode rightNode = findKey(value, node.getRightChild());

        if (leftNode != null) {
            return leftNode;
        }

        if (rightNode != null) {
            return rightNode;
        }

        return null;
    }

    @Override
    public void preOrderTraverse() {
        this.preOrderTraverse(root);
    }

    private void preOrderTraverse(TreeNode node) {
        if (node == null) {
            return;
        }
        // d输出
        System.out.print(node.getData() + &quot; &quot;);
        // l处理
        preOrderTraverse(node.getLeftChild());
        // r处理
        preOrderTraverse(node.getRightChild());
    }

    @Override
    public void inOrderTraverse() {
        this.inOrderTraverse(root);
    }

    private void inOrderTraverse(TreeNode node) {
        if (node == null) {
            return;
        }
        // l处理
        inOrderTraverse(node.getLeftChild());
        // d输出
        System.out.print(node.getData() + &quot; &quot;);
        // r处理
        inOrderTraverse(node.getRightChild());
    }

    @Override
    public void postOrderTraverse() {
        this.postOrderTraverse(root);
    }

    private void postOrderTraverse(TreeNode node) {
        if (node == null) {
            return;
        }
        // l处理
        postOrderTraverse(node.getLeftChild());
        // r处理
        postOrderTraverse(node.getRightChild());
        // d输出
        System.out.print(node.getData() + &quot; &quot;);
    }

    @Override
    public void preOrderByStack() {
        Deque&lt;TreeNode&gt; stack = new LinkedList&lt;&gt;();
        if (root == null) {
            return;
        }

        // 心法：以当前node移动，根据DLR、LDR、LRD的顺序去如何存取到stack中去
        // 指向树的当前移动node点
        TreeNode current = root;
        List&lt;Object&gt; result = new ArrayList&lt;&gt;();
        while (current != null || !stack.isEmpty()) {
            // 将current node的所有左子节点全放到栈里，一致循环直到左子node为null
            while (current != null) {
                // 输出
                result.add(current.getData());
                stack.push(current);
                // 要移动current node的位置给current node (即left node)
                current = current.getLeftChild();
            }

            // 如果栈不为空，那就从栈中弹出栈顶元素
            // 将current node的right node给 current node，供下次循环找其所有的left node
            if (!stack.isEmpty()) {
                current = stack.pop();
                current = current.getRightChild();
            }
        }
        System.out.println(result);
    }

    @Override
    public void inOrderByStack() {
        Deque&lt;TreeNode&gt; stack = new LinkedList&lt;&gt;();
        if (root == null) {
            return;
        }

        // 心法：以当前node移动，根据DLR、LDR、LRD的顺序去如何存取到stack中去
        // 指向树的当前移动node点
        TreeNode current = root;
        List&lt;Object&gt; result = new ArrayList&lt;&gt;();
        while (current != null || !stack.isEmpty()) {
            // 将current node的所有左子节点全放到栈里，一致循环直到左子node为null
            while (current != null) {
                stack.push(current);
                // 要移动current node的位置给current node (即left node)
                current = current.getLeftChild();
            }

            // 如果栈不为空，那就从栈中弹出栈顶元素，输出
            // 将current node的right node给 current node，供下次循环找其所有的left node
            if (!stack.isEmpty()) {
                current = stack.pop();
                result.add(current.getData());
                current = current.getRightChild();
            }
        }
        System.out.println(result);
    }

    @Override
    public void postOrderByStack() {

        // 方式一：
        Deque&lt;TreeNode&gt; stack = new LinkedList&lt;&gt;();
        if (root == null) {
            return;
        }
        List&lt;Object&gt; result = new ArrayList&lt;&gt;();
        // 指向树的当前移动node点
        TreeNode current = null;
        // 指向当前移动node的其中一个子节点(即，栈上的上一个栈顶)
        TreeNode tmpChildNode = null;

        stack.push(root);
        while (!stack.isEmpty()) {
            current = stack.peek();
            if ((current.getLeftChild() == null &amp;&amp; current.getRightChild() == null) || current.getLeftChild() == tmpChildNode || current
                    .getRightChild() == tmpChildNode) {
                result.add(current.getData());
                stack.pop();
                tmpChildNode = current;
            } else {
                // 先添加right child node ，因为栈是LIFO
                if (current.getRightChild() != null) {
                    stack.push(current.getRightChild());
                }
                // 再添加left child node ，因为栈是LIFO
                if (current.getLeftChild() != null) {
                    stack.push(current.getLeftChild());
                }
            }
        }
        System.out.println(result);


        // 方式二
        // Deque&lt;TreeNode&gt; stack = new LinkedList&lt;&gt;();
        // if (root == null) {
        //     return;
        // }
        //
        // // 心法：以当前node移动，根据DLR、LDR、LRD的顺序去如何存取到stack中去
        // // 指向树的当前移动node点
        // TreeNode current = root;
        // List&lt;Object&gt; result = new ArrayList&lt;&gt;();
        // while (current != null || !stack.isEmpty()) {
        //     // 将current node的所有右子节点全放到栈里，一致循环直到右子node为null
        //     while (current != null) {
        //         stack.push(current);
        //         // 要移动current node的位置给current node (即right node)
        //         result.add(current.getData());
        //         current = current.getRightChild();
        //     }
        //
        //     // 如果栈不为空，那就从栈中弹出栈顶元素，输出
        //     // 将current node的left node给 current node，供下次循环找其所有的right node
        //     if (!stack.isEmpty()) {
        //         current = stack.pop();
        //         current = current.getLeftChild();
        //     }
        // }
        // // 反转下结果
        // Collections.reverse(result);
        // System.out.println(result);
    }

    @Override
    public void levelOrderByQueue() {
        Deque&lt;TreeNode&gt; queue = new LinkedList&lt;&gt;();
        if (root == null) {
            return;
        }
        List&lt;Object&gt; result = new ArrayList&lt;&gt;();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            // 遍历将stack里元素弹出
            for (int i = 0; i &lt; len; i++) {
                TreeNode node = queue.poll();
                result.add(node.getData());
                TreeNode leftChild = node.getLeftChild();
                TreeNode rightChild = node.getRightChild();
                if (leftChild != null) {
                    queue.offer(leftChild);
                }
                if (rightChild != null) {
                    queue.offer(rightChild);
                }
            }
        }
        System.out.println(result);
    }
}
</code></pre>
<h3 id="4-4-测试代码"><a href="#4-4-测试代码" class="headerlink" title="4-4.测试代码"></a>4-4.测试代码</h3><p>造的tree就是我们前面文章一直分析的树</p>
<img src="/blog/images/da/da-btree-foreach-complex-example.png" width="650px">

<pre><code class="java">public class MyListBinaryTreeTest {
    public static void main(String[] args) {
        TreeNode root = genBTree();

        MyListBinaryTree myListBinaryTree = new MyListBinaryTree(root);

        System.out.println(&quot;是否为空：&quot; + myListBinaryTree.isEmpty());
        System.out.println(&quot;树的高度：&quot; + myListBinaryTree.getHeight());
        System.out.println(&quot;树节点数：&quot; + myListBinaryTree.size());

        System.out.println(&quot;查找3： &quot; + myListBinaryTree.findKey(3));
        System.out.println(&quot;查找20：&quot; + myListBinaryTree.findKey(20));

        System.out.println(&quot;前序递归遍历：&quot;);
        myListBinaryTree.preOrderTraverse();
        System.out.println(&quot;&quot;);
        System.out.println(&quot;中序递归遍历：&quot;);
        myListBinaryTree.inOrderTraverse();
        System.out.println(&quot;&quot;);
        System.out.println(&quot;后序递归遍历：&quot;);
        myListBinaryTree.postOrderTraverse();
        System.out.println(&quot;&quot;);

        System.out.println(&quot;前序栈遍历：&quot;);
        myListBinaryTree.preOrderByStack();
        System.out.println(&quot;&quot;);
        System.out.println(&quot;中序栈遍历：&quot;);
        myListBinaryTree.inOrderByStack();
        System.out.println(&quot;&quot;);
        System.out.println(&quot;后序栈遍历：&quot;);
        myListBinaryTree.postOrderByStack();
        System.out.println(&quot;&quot;);
        System.out.println(&quot;水平队列遍历：&quot;);
        myListBinaryTree.levelOrderByQueue();
    }

    private static TreeNode genBTree() {
        TreeNode treeNode6 = new TreeNode(6, null, null);
        TreeNode treeNode7 = new TreeNode(7, null, null);
        TreeNode treeNode4 = new TreeNode(4, treeNode6, treeNode7);

        TreeNode treeNode9 = new TreeNode(9, null, null);
        TreeNode treeNode8 = new TreeNode(8, null, treeNode9);
        TreeNode treeNode5 = new TreeNode(5, treeNode8, null);

        TreeNode treeNode2 = new TreeNode(2, treeNode4, treeNode5);

        TreeNode treeNode10 = new TreeNode(10, null, null);
        TreeNode treeNode12 = new TreeNode(12, null, null);
        TreeNode treeNode11 = new TreeNode(11, null, treeNode12);

        TreeNode treeNode3 = new TreeNode(3, treeNode10, treeNode11);

        return new TreeNode(1, treeNode2, treeNode3);
    }
}
</code></pre>
<p><strong>结果</strong></p>
<pre><code class="txt">是否为空：false
树的高度：4
树节点数：12
查找3： TreeNode{data=3, leftChild=10, rightChild=11}
查找20：null
前序递归遍历：
1 2 4 6 7 5 8 9 3 10 11 12 
中序递归遍历：
6 4 7 2 8 9 5 1 10 3 11 12 
后序递归遍历：
6 7 4 9 8 5 2 10 12 11 3 1 
前序栈遍历：
[1, 2, 4, 6, 7, 5, 8, 9, 3, 10, 11, 12]

中序栈遍历：
[6, 4, 7, 2, 8, 9, 5, 1, 10, 3, 11, 12]

后序栈遍历：
[6, 7, 4, 9, 8, 5, 2, 10, 12, 11, 3, 1]

水平队列遍历：
[1, 2, 3, 4, 5, 10, 11, 6, 7, 8, 12, 9]</code></pre>
<h2 id="5-链接"><a href="#5-链接" class="headerlink" title="5.链接"></a>5.链接</h2><ul>
<li><a href="https://blog.csdn.net/jun2016425/article/details/54581407" target="_blank" rel="noopener">二叉树特性及证明</a></li>
<li><a href="https://blog.csdn.net/qq_41795143/article/details/103292676" target="_blank" rel="noopener">二叉树性质及证明</a></li>
</ul>

      
       <hr><span style="font-style: italic;color: gray;"> 转载请注明来源，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 157162006@qq.com </span>
    </div>
</article>


<p>
    <a  class="dashang" onclick="dashangToggle()">赏</a>
</p>


<div class="article_copyright">
    <p><span class="copy-title">文章标题:</span>数据结构和算法5-非线性-树</p>
    <p><span class="copy-title">字数:</span><span class="post-count">6.2k</span></p>
    <p><span class="copy-title">本文作者:</span><a  title="沐雨云楼">沐雨云楼</a></p>
    <p><span class="copy-title">发布时间:</span>2020-07-04, 15:09:47</p>
    <p><span class="copy-title">最后更新:</span>2020-09-12, 21:21:47</p>
    <span class="copy-title">原始链接:</span><a class="post-url" href="/blog/2020/07/04/data-structures-algorithms-tree/" title="数据结构和算法5-非线性-树">https://iworkh.gitee.io/blog/2020/07/04/data-structures-algorithms-tree/</a>
    <p>
        <span class="copy-title">版权声明:</span><i class="fa fa-creative-commons"></i> <a rel="license noopener" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank" title="CC BY-NC-SA 4.0 International" target = "_blank">&#34;署名-非商用-相同方式共享 4.0&#34;</a> 转载请保留原文链接及作者。
    </p>
</div>



    <div id="comments"></div>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.css">

<script type="text/javascript">
    $.getScript('/blog/js/gitalk.js', function () {
        var gitalk = new Gitalk({
            clientID: 'e4a269e1ae1600031361',
            clientSecret: '6f3f981cbc49dd802fde779697d8f01da3a77981',
            repo: 'iworkh.github.io',
            owner: 'iworkh',
            admin: ['iworkh'],
            id: decodeURI(location.pathname),
            distractionFreeMode: 'true',
            language: 'zh-CN',
            perPage: parseInt('10',10)
        })
        gitalk.render('comments')
    })
</script>




    
        <!-- MathJax配置，可通过单美元符号书写行内公式等 -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
    "HTML-CSS": {
        preferredFont: "TeX",
        availableFonts: ["STIX","TeX"],
        linebreaks: { automatic:true },
        EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
        inlineMath: [ ["$", "$"], ["\\(","\\)"] ],
        processEscapes: true,
        ignoreClass: "tex2jax_ignore|dno",
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
        equationNumbers: { autoNumber: "AMS" },
        noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" } },
        Macros: { href: "{}" }
    },
    messageStyle: "none"
    });
</script>
<!-- 给MathJax元素添加has-jax class -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>
<!-- 通过连接CDN加载MathJax的js代码 -->
<script type="text/javascript" async
        src="//cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/MathJax.js?config=TeX-MML-AM_CHTML">
</script>
<input type="hidden" id="MathJax-js"
        value="//cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/MathJax.js?config=TeX-MML-AM_CHTML">
</input>
    




    </div>
    <div class="copyright">
        <p class="footer-entry">©2020 iworkh</p>
<!--<p class="footer-entry">Built with <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/yelog/hexo-theme-3-hexo" target="_blank">3-hexo</a> theme</p>-->

    </div>
    <div class="full-toc">
        <button class="full" data-title="切换全屏 快捷键 s"><span class="min "></span></button>
<button class="post-toc-menu" data-title="打开TOC 快捷键 w"><span class="post-toc-menu-icons"></span></button>
<div class="post-toc"><span class="post-toc-title">目录</span>
    <div class="post-toc-content">

    </div>
</div>
<a class="" id="rocket" ></a>

    </div>
</div>
<div class="acParent"></div>

<div class="hide_box" onclick="dashangToggle()"></div>
<div class="shang_box">
    <a class="shang_close"  onclick="dashangToggle()">×</a>
    <div class="shang_tit">
        <p>喜欢就点赞,疼爱就打赏</p>
    </div>
    <div class="shang_payimg">
        <div class="pay_img">
            <img src="/blog/img/alipay.jpg" class="alipay" title="扫码支持">
            <img src="/blog/img/weixin.jpg" class="weixin" title="扫码支持">
        </div>
    </div>
    <div class="shang_payselect">
        <span><label><input type="radio" name="pay" checked value="alipay">支付宝</label></span><span><label><input type="radio" name="pay" value="weixin">微信</label></span>
    </div>
</div>


</body>
<script src="/blog/js/jquery.pjax.js?v=1.0.1" ></script>

<script src="/blog/js/script.js?v=1.0.1" ></script>
<script>
    var img_resize = 'default';
    /*作者、标签的自动补全*/
    $(function () {
        $('.search').AutoComplete({
            'data': ['@沐雨云楼','@iworkh','#ai','#attr','#aysnc','#beanmap','#bigdecimal','#blog','#chrome','#dict','#dll','#docker','#domain','#fastjson','#func','#git','#github','#hadoop','#hexo','#idea','#iworkh','#jackson','#java','#jdni','#jfinalshell','#joplin','#JPA','#lock','#markdowm','#maven','#mock','#mq','#mycat','#mysql','#nginx','#notebook','#plan','#powermock','#python','#redis','#rest','#sharding-jdbc','#spark','#springboot','#test','#tool','#tools','#tornado','#transactional','#web','#windows','#wtforms','#zookeeper','#分库分表','#分页','#命令','#工具','#并发','#序列化','#微服务','#性能分析','#手册','#有道云','#标签','#模板','#百度云盘','#结构和算法','#计划','#迁移','#面试',],
            'itemHeight': 20,
            'width': 418
        }).AutoComplete('show');
    })
    function initArticle() {
        /*渲染对应的表格样式*/
        
            $(".post .pjax table").addClass("green_title");
        

        /*渲染打赏样式*/
        
        $("input[name=pay]").on("click", function () {
            if($("input[name=pay]:checked").val()=="weixin"){
                $(".shang_box .shang_payimg .pay_img").addClass("weixin_img");
            } else {
                $(".shang_box .shang_payimg .pay_img").removeClass("weixin_img");
            }
        })
        

        /*高亮代码块行号*/
        
        $('pre code').each(function(){
            var lines = $(this).text().trim().split('\n').length, widther='';
            if (lines>99) {
                widther = 'widther'
            }
            var $numbering = $('<ul/>').addClass('pre-numbering ' + widther).attr("unselectable","on");
            $(this).addClass('has-numbering ' + widther)
                    .parent()
                    .append($numbering);
            for(var i=1;i<=lines;i++){
                $numbering.append($('<li/>').text(i));
            }
        });
        

        /*访问数量*/
        
        $.getScript("//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js");
        

        /*代码高亮，行号对齐*/
        $('.pre-numbering').css('line-height',$('.has-numbering').css('line-height'));

        
        
    }

    /*打赏页面隐藏与展示*/
    
    function dashangToggle() {
        $(".shang_box").fadeToggle();
        $(".hide_box").fadeToggle();
    }
    

</script>

<!--加入行号的高亮代码块样式-->

<style>
    pre{
        position: relative;
        margin-bottom: 24px;
        border-radius: 10px;
        border: 1px solid #e2dede;
        background: #FFF;
        overflow: hidden;
    }
    code.has-numbering{
        margin-left: 30px;
    }
    code.has-numbering.widther{
        margin-left: 35px;
    }
    .pre-numbering{
        margin: 0px;
        position: absolute;
        top: 0;
        left: 0;
        width: 20px;
        padding: 0.5em 3px 0.7em 5px;
        border-right: 1px solid #C3CCD0;
        text-align: right;
        color: #AAA;
        background-color: #fafafa;
    }
    .pre-numbering.widther {
        width: 35px;
    }
</style>

<!--自定义样式设置-->
<style>
    
    
    .nav {
        width: 442px;
    }
    .nav.fullscreen {
        margin-left: -442px;
    }
    .nav-left {
        width: 120px;
    }
    
    
    @media screen and (max-width: 1468px) {
        .nav {
            width: 442px;
        }
        .nav.fullscreen {
            margin-left: -442px;
        }
        .nav-left {
            width: 150px;
        }
    }
    
    
    @media screen and (max-width: 1024px) {
        .nav {
            width: 442px;
            margin-left: -442px
        }
        .nav.fullscreen {
            margin-left: 0;
        }
        .nav .hide-list.fullscreen {
            left: 442px
        }
    }
    
    @media screen and (max-width: 426px) {
        .nav {
            width: 100%;
        }
        .nav-left {
            width: 100%;
        }
    }
    
    
    .nav-right .title-list nav a .post-title, .nav-right .title-list #local-search-result a .post-title {
        color: #383636;
    }
    
    
    .nav-right .title-list nav a .post-date, .nav-right .title-list #local-search-result a .post-date {
        color: #5e5e5f;
    }
    
    
    .nav-right nav a.hover, #local-search-result a.hover{
        background-color: #e2e0e0;
    }
    
    

    /*列表样式*/
    
    .post .pjax article .article-entry>ol, .post .pjax article .article-entry>ul, .post .pjax article>ol, .post .pjax article>ul{
        border: #e2dede solid 1px;
        border-radius: 10px;
        padding: 10px 32px 10px 56px;
    }
    .post .pjax article .article-entry li>ol, .post .pjax article .article-entry li>ul,.post .pjax article li>ol, .post .pjax article li>ul{
        padding-top: 5px;
        padding-bottom: 5px;
    }
    .post .pjax article .article-entry>ol>li, .post .pjax article .article-entry>ul>li,.post .pjax article>ol>li, .post .pjax article>ul>li{
        margin-bottom: auto;
        margin-left: auto;
    }
    .post .pjax article .article-entry li>ol>li, .post .pjax article .article-entry li>ul>li,.post .pjax article li>ol>li, .post .pjax article li>ul>li{
        margin-bottom: auto;
        margin-left: auto;
    }
    

    /* 背景图样式 */
    
    


    /*引用块样式*/
    

    /*文章列表背景图*/
    

    
</style>






<div class="mobile-menus-out" >

</div>
<div class="mobile-menus">
    
    
    
    <a class="dynamic-menu " target="_blank"  href="https://pgmanor.gitee.io/blog/">pgmanor</a>
    
    
    <a class="dynamic-menu " target="_blank"  href="https://www.iworkh.com/manualIt/Category/scopeDev/">iworkh</a>
    
    
    <a class="dynamic-menu " target="_blank"  href="https://gitee.com/iworkh">gitee</a>
    
</div>


<div style="position:absolute; bottom: 0; right: 0;">
    <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=150 height=40 src="//music.163.com/outchain/player?type=2&id=1323150930&auto=0&height=32"></iframe>
</div>

</html>
